package th.retrofit.lib;

import java.util.LinkedList;
import java.util.List;

/**
 * 给定一个单词数组和一个长度maxWidth，重新排版单词，使其成为每行恰好有maxWidth个字符，且左右两端对齐的文本。
 *
 * 你应该使用“贪心算法”来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格' '填充，使得每行恰好有 maxWidth个字符。
 *
 * 要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
 *
 * 文本的最后一行应为左对齐，且单词之间不插入额外的空格。
 *
 * 说明:
 *
 * 单词是指由非空格字符组成的字符序列。
 * 每个单词的长度大于 0，小于等于maxWidth。
 * 输入单词数组 words至少包含一个单词。
 */
public class Solution68 {

    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> results = new LinkedList<>();
        List<String> temp = new LinkedList<>();
        int wLen = words.length;
        int i = 0;
        while (i < wLen) {
            for (int j = 0; i < wLen && j + words[i].length() <= maxWidth; i++) {
                temp.add(words[i]);
                j += words[i].length();
                j++;
            }
            if (i == wLen) {
                StringBuilder builder = new StringBuilder();
                for (int j = 0; j < temp.size(); j++) {
                    builder.append(temp.get(j));
                    if (builder.length() < maxWidth) {
                        builder.append(' ');
                    }
                }
                int bLen = builder.length();
                for (int j = 0; j < maxWidth - bLen; j++) {
                    builder.append(' ');
                }
                results.add(builder.toString());
            } else if (temp.size() == 1) {
                int bLen = temp.get(0).length();
                StringBuilder builder = new StringBuilder(temp.get(0));
                for (int j = 0; j < maxWidth - bLen; j++) {
                    builder.append(' ');
                }
                results.add(builder.toString());
            } else {
                int cNum = 0;
                int tSize = temp.size();
                for (int j = 0; j < tSize; j++) {
                    cNum += temp.get(j).length();
                }
                int spaceCount = maxWidth - cNum;
                int perCount = spaceCount / (tSize - 1);
                int eCount = spaceCount % (tSize - 1);
                char[] spaces = new char[perCount];
                for (int j = 0; j < perCount; j++) {
                    spaces[j] = ' ';
                }
                StringBuilder builder = new StringBuilder();
                for (int j = 0; j < tSize; j++) {
                    builder.append(temp.get(j));
                    if (j < tSize - 1) {
                        builder.append(spaces);
                    }
                    if (j < eCount) {
                        builder.append(' ');
                    }
                }
                results.add(builder.toString());
            }
            temp.clear();
        }
        return results;
    }

    public static void main(String[] args) {
        String[] words = new String[]{"Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"};
        int maxWidth = 20;
        List<String> results = new Solution68().fullJustify(words, maxWidth);
        results.forEach(System.out::println);
    }

}
